package leetcode.editor.cn;

public class Q426TreeToDoublyList {
    static TreeNode pre, head;
    public static TreeNode treeToDoublyList(TreeNode root) {
        if (root == null) return null;
        dfs(root);
        // 此时pre为二叉树中的最右侧节点，最大的
        head.right = pre;
        pre.left = head;
        return head;
    }

    public static void dfs(TreeNode cur) {
        if (cur == null) return;
        dfs(cur.left);
        // 是头节点
        if (pre == null) {
            head = cur;
        } else {
            pre.right = cur;
        }
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(5);

        treeToDoublyList(root);
        System.out.println();
    }
}
